1. Field of the Invention
This invention relates generally to computer program execution systems, e.g., optimizing compilers, and more specifically, to a system and method for sampling executing programs at selected program yield points to enable the characterization of runtime program behavior.
2. Discussion of the Prior Art
Many modern programming language runtime environments and tools can benefit from runtime feedback from a program. For example, Java virtual machines may use runtime feedback to guide optimization of the running program. As another example, program understanding tools may gather runtime information and report summaries to the user.
Since running programs may potentially generate vast quantities of runtime data, many systems use statistical sampling to reduce the volume of information. With this well-known technique, the system collects only a subset, or sample, of the total relevant runtime information, and infers properties of the program by extrapolating from the sample.
Although sampling is a well-known principle, a system that implements sampling faces potentially difficult engineering tradeoffs. The system must implement a sampling mechanism that gathers an interesting subset of the data, while minimizing runtime overhead. For some applications, the system must implement a mechanism that collects multiple independent samples. The system must extrapolate from the sampled data to recover the information it desires, a non-trivial task in some cases. Also, for some applications, the system must rely on compiler support to provide information about the program, and integrate this support with the runtime system.
Many compilers and programming tools collect runtime information to characterize the behavior of a running program. In order to collect runtime information, the system must periodically interrupt the running program and record information regarding the current state of execution.
There are two previous approaches to interrupting programs to collect runtime information. In the first approach, the system interrupts the program at any arbitrary instruction. For example, the DCPI profiling tool described in the reference to J. M. Andersen, L. M. Berc, J. Dean, et al. entitled “Continuous profiling: Where have all the cycles gone?”, Technical Note 1997-016a, Digital Systems Research Center, September 1997, interrupts the program after executing a fixed number of instructions. An advantage of this approach is that the mechanism works for any binary program, and requires no participation by the compiler.
In the second approach, the system identifies distinguished program points at which it collects information. For example, the IBM family MMI Development Kits for Java supports invocation counters at method entries. With this approach, the compiler or interpreter conspires with the profiling system to interrupt the program at particular points. The advantage of this approach is that the compiler or interpreter can record detailed information specific to these distinguished program points. So, for example, the MMI systems record the identity of the interrupted method at each invocation counter point.
It would be highly desirable to provide improved methods and mechanisms for collecting executing program runtime information. In particular it would be highly desirable to provide improved methods and mechanisms for collecting executing program runtime information at a subset of distinguished program points in a manner so as to reduce runtime overhead.